/**
 * 交错字符串
 *
 * 给定三个字符串 s1、s2、s3，请你帮忙验证 s3 是否是由 s1 和 s2 交错 组成的。
 * 两个字符串 s 和 t 交错 的定义与过程如下，其中每个字符串都会被分割成若干 非空 子字符串：
 * s = s1 + s2 + ... + sn
 * t = t1 + t2 + ... + tm
 * |n - m| <= 1
 * 交错 是 s1 + t1 + s2 + t2 + s3 + t3 + ... 或者 t1 + s1 + t2 + s2 + t3 + s3 + ...
 * 注意：a + b 意味着字符串 a 和 b 连接。
 *
 * 示例 1：
 * 输入：s1 = "aabcc", s2 = "dbbca", s3 = "aadbbcbcac"
 * 输出：true
 *
 * 示例 2：
 * 输入：s1 = "aabcc", s2 = "dbbca", s3 = "aadbbbaccc"
 * 输出：false
 *
 * 示例 3：
 * 输入：s1 = "", s2 = "", s3 = ""
 * 输出：true
 *
 * 提示：
 * 0 <= s1.length, s2.length <= 100
 * 0 <= s3.length <= 200
 * s1、s2、和 s3 都由小写英文字母组成
 *
 * 进阶：您能否仅使用 O(s2.length) 额外的内存空间来解决它?
 */

/**
 * 动态规划
 * dp[i][j] : s1 i, s2 j, 是否能组成 s3 i + j,
 * dp[i][j] : s1[i] == s3[i + j] && dp[i - 1][j]
 *            s2[j] == s3[i + j] && dp[i][j - 1]
 * 这里初始化要注意, 要连着的才能初始化, 要是没连着, 直接
 * break 就可以了
 * 时间复杂度 : O(n ^ 2)
 * 空间复杂度 : O(n ^ 2)
 */

public class Main {
    public boolean isInterleave(String s1, String s2, String s3) {

        // 长度
        int n1 = s1.length(), n2 = s2.length();

        // 判断长度是否符合条件
        if (n1 + n2 != s3.length()) {
            return false;
        }

        boolean[][] dp = new boolean[n1 + 1][n2 + 1];

        // 这里为了方便偏移, 我们在前面加一个 " "
        s1 = " " + s1;
        s2 = " " + s2;
        s3 = " " + s3;

        // 初始化
        for (int i = 1; i <= n1; i++) {
            if (s1.charAt(i) != s3.charAt(i)) {
                break;
            }
            dp[i][0] = true;
        }

        for (int j = 1; j <= n2; j++) {
            if (s2.charAt(j) != s3.charAt(j)) {
                break;
            }
            dp[0][j] = true;
        }

        // 别忘了第一个位置也要初始化
        dp[0][0] = true;

        for (int i = 1; i <= n1; i++) {
            for (int j = 1; j <= n2; j++) {

                // 符合条件的两种, 这个位置就是合格的
                dp[i][j] = (s1.charAt(i) == s3.charAt(i + j) && dp[i - 1][j])
                        || (s2.charAt(j) == s3.charAt(i + j) && dp[i][j - 1]);
            }
        }

        // 返回结果
        return dp[n1][n2];
    }
}